package com.lijing.BackTracing1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description 找出所有相加之和为 n 的 k 个数的组合。
 * 组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
 * @title: Combination2
 * @Author LiJing
 * @Date: 2021/4/53:17 下午
 * @Version 1.0
 */
public class Combination2 {
    static List<LinkedList<Integer>> result = new ArrayList<>();
    static LinkedList<Integer> path = new LinkedList<>();
    static int pathSum = 0;
    public static void main(String[] args) {
        backTrack(1,4,2);
        System.out.println(result);
    }

    public static void backTrack(int startIndex, int n, int k){
        if (pathSum > n){
            return;
        }
        if (path.size() == k){
            if (pathSum == n){
                result.add(new LinkedList<>(path));
            }
            return;
        }

        for (int i = startIndex; i <= 9-(k-path.size())+1; i++) {
            //处理当前节点
            path.addLast(i);
            pathSum += i;
            backTrack(i+1,n,k);
            int temp = path.removeLast();
            pathSum -= temp;
        }
    }
}
